#pragma once


#include "red_black_tree.h"
#include "pair.h"

namespace self
{
	template <class key>
	class set
	{
	public:

		struct KeyOfSet
		{
			key operator()(const key& k)
			{
				return k;
			}
		};

		typedef typename redBlackTree<key,key,KeyOfSet>::const_iterator iterator;
		typedef typename redBlackTree<key, key, KeyOfSet>::const_iterator const_iterator;
		typedef typename redBlackTree<key, key, KeyOfSet>::const_reverse_iterator reverse_iterator;
		typedef typename redBlackTree<key,  key, KeyOfSet>::const_reverse_iterator const_reverse_iterator;

		typedef redBlackTreeNode<key> Node;

		iterator begin() const
		{
			return _rb.begin();
		}

		iterator end() const
		{
			return _rb.end();
		}

		const_reverse_iterator rbegin() const
		{
			return _rb.rbegin();
		}

		const_reverse_iterator rend() const
		{
			return _rb.rend();
		}

		set()
		{}

		template<class InputIterator>
		set(InputIterator first,InputIterator end)
		{
			while (first != end)
			{
				insert(*first);
				++first;
			}
		}

		set(const set<key>& s)
		{
			set<key> tmp(s.begin(), s.end());
			swap(tmp);
		}

		set& operator=(set s)
		{
			swap(s);
			return *this;
		}

		void swap(set<key>& tmp)
		{
			Node* root = _rb.get_root();
			_rb.get_root() = tmp._rb.get_root();
			tmp._rb.get_root() = root;

		}

		pair<iterator,bool> insert(const key& k)
		{
			pair<typename redBlackTree<key, key, KeyOfSet>::iterator, bool> p(_rb.insert(k));
			return pair<iterator, bool>(p.first, p.second);
		}

		iterator find(const key& k)
		{
			auto it = begin();
			while (it != end())
			{
				if (*it == k)
				{
					return it;
				}
				++it;
			}
			return end();
		}

		size_t size()
		{
			return _rb.size();
		}

		void clear()
		{
			_rb.clear(_rb.get_root());
			_rb.get_root() = nullptr;
		}

		bool empty()
		{
			return _rb.get_root() == nullptr;
		}

	protected:
		redBlackTree<key, key, KeyOfSet> _rb;
	};


	template <class key>
	class multiset : public set<key>
	{
		typedef typename set<key>::iterator iterator;
		typedef set<key>::KeyOfSet KeyOfSet;
	public:
		pair<iterator, bool> insert(const key& k)
		{
			pair<typename redBlackTree<key, key, KeyOfSet>::iterator, bool> p(this->_rb.insert(k));
			return pair<iterator, bool>(p.first, p.second);
		}
	};
}